Study of the effect of cost policies in the convergence of selfish strategies in Pure Nash Equilibria in Congestion Games

摘要

In this work we study of competitive situations among users of a set ofglobal resources. More precisely we study the effect of cost policies used bythese resources in the convergence time to a pure Nash equilibrium. The work isdivided in two parts. In the theoretical part we prove lower and upper boundson the convergence time for various cost policies. We then implement all themodels we study and provide some experimental results. These results followsthe theoretical with one exception which is the most interesting among theexperiments. In the case of coalitional users the theoretical upper bound ispseudo-polynomial to the number of users but the experimental results showsthat the convergence time is polynomial.